package sorting;

public class MergeSort {

	static int[] array = new int[] { 5, 9, 4, 0, 14, 6, 14, 99, 3, 44, 17 };

	public static void main(String[] args) {
		
		mergeSort(array, 0, array.length - 1);

		printArray(array);

	}

	private static void mergeSort(int[] array, int l, int r) {

		int middle = (l+r) >> 1;
		if(l < r) {
			mergeSort(array, l, middle);
			mergeSort(array, middle + 1, r);
			
			merge(array, l, middle, r);
		}
		
	}

	private static void merge(int[] array, int l, int middle, int r) {
		
		int tempArray[] = new int[r - l + 1];
		int i = l;
		int j = middle + 1;
		int index = 0;
		
		while(i <= middle && j <= r) {
			tempArray[index] = array[i];
			if(tempArray[index] > array[j]) {
				tempArray[index] = array[j];
				j++;
			} else {
				i++;
			}
			index++;
		}
		
		while(i <= middle) {
			tempArray[index++] = array[i++];
		}
		
		while(j <= r) {
			tempArray[index++] = array[j++];
		}
		
		for(int k=l; k<=r; k++) {
			array[k] = tempArray[k-l];
		}
		
	}

	private static void printArray(int[] array2) {
		for (int a : array) {
			System.out.print(a + " ");
		}
	}
}
